Each time these cells pass through a node of a switching system, each is subjected to a variable delay as a function of the path inside the switching network containing this node. The sub-cells of a same cell are linked in such a way, that they follow the same path and are subjected to the same delay. The sub-cells of a same cell therefore maintain their initial order at the switching network output; by contrast, the cells do not always maintain their initial order because of the delay dispersion. A resequencing device has the function of resetting these cells to their initial order.
European Patent Application No. 0,438,415, corresponding to International Publication No. WO 91/02419 and U.S. Pat. No. 5,127,000, describes a resequencing process that consists in retarding each cell by a determined delay in a way that the total delay imposed by the switching network and the resequencing device has a constant value for all the cells, where this value is generally chosen larger than the maximum delay the switching network can create. If the total delay is less than the maximum delay value the switching network can create, the probability of disturbing the initial order is not zero, it is a function of the chosen value of the total delay. This known process has two variations.
A first variation consists in: assigning a time stamp to each cell entering the switching network, which indicates at what moment the cell entered the switching network; to extract the time stamp from each cell leaving the switching network; to store each cell leaving the network until the time indicated by the time stamp generator is the same as the time indicated by the cell's time stamp, plus the chosen total delay; then to allow the cell to be transmitted through a resequencing device outlet. The transmission actually takes place as soon as the outlet and the cell's destination are available.
According to this variation, the initial order of the cells is restored without the need to measure or estimate the delayed transition of each cell through the switching network. By contrast, the time furnished by the time stamp generator must be available in a device located at the network input for the assignment of time stamps, and must be simultaneously available in a resequencing device located at the network outlet, to allow each cell to be transmitted at a convenient moment.
According to another variation of this known process, each cell leaving the network is assigned a label whose value is an estimate of the delay undergone by the cell during its passage through the network; and to subject each cell to an additional delay whose length is equal to the difference between the predetermined value of the total delay and the estimated value of the delayed passage through the network, where the latter is read from the label associated with each cell. This variation has the advantage of not needing a device to assign time stamps to the cells arriving at the inputs of the switching network.
This patent application also describes a resequencing device that uses the first variation of the process mentioned above, for cells that each consist of a variable number of fixed length sub-cells. Each output of a node is equipped with one of these devices. The device contains:
a first time stamp generator which supplies a value incremented by one unit for each time interval corresponding to a sub-cell, with a cycle length at least equal to the total predetermined delay so that all cells are uniformly delayed; PA1 a buffer memory with one input coupled to an input of the resequencing device, and with an output coupled to an output of the resequencing device; where each memory address has a capacity that is equal to one sub-cell; PA1 a control circuit for this buffer memory, to supply the addresses of free sites in this buffer memory for storing the sub-cells of each cell received by the resequencing device; PA1 a read/write pointer associated with the buffer memory; PA1 a memory of addresses with the sites corresponding respectively to the various possible time stamp values; each site of this address memory stores a starting and an ending pointer of the list which are the respective addresses in the buffer memory, of the first and the last sub-cell of a series containing all the cells having the same time stamp; PA1 a link memory with the same addresses as the buffer memory, to retain the links between the addresses of all the sub-cells having the same time stamp, and to retain the links between the addresses of the sub-cells belonging to the cells to be transmitted in succession; PA1 a write pointer associated with this address memory to store in each site the first and the last address of a list of site addresses of the buffer memory, containing all the sub-cells of all the cells with the same time stamp; PA1 a read pointer associated with the address memory, with a cyclic function, to successively read the contents of the sites in this address memory, in order to read sub-cells in the buffer memory in addresses that correspond to time stamps that cross in a regular manner. PA1 a buffer memory for storing all the sub-cells of each cell received by the resequencing device; PA1 an address memory to enter the address of the buffer memory containing the first sub-cell of each cell; PA1 means to find the address in the address memory that contains the first sub-cell of a cell, after the waiting delay of the latter has expired, and an output to emit this cell is available; characterized in that the means to find the address of the buffer memory containing the first sub-cell of a cell, which means contain: PA1 a memory of waiting cells, of the type that is accessible by its content, to memorize an identifier of the waiting cell when a cell is stored in the buffer memory; this identifier is stored in an address that is identical to the one where the address FSA of the first sub-cell is stored in the address memory; the identifier is composed of a time stamp that identifies a time interval during which the waiting delay of that cell expires, and the identity of at least one output through which it is to be emitted; PA1 means to find the identifier of each cell in the waiting cell memory when the waiting delay expires, and for each found identifier to supply the address of the waiting cell memory containing this found identifier; PA1 queuing memories, respectively associated with the outputs of the node, and accessible by their content, to memorize an order number for each cell intended for the output associated with the memory under consideration; PA1 means to determine and record an order number in a queuing memory, at the address supplied by the means to find the identifier of each cell when its waiting delay expires; PA1 means to find, in an ascending order, each number entered into the queuing memory of an output, when this output becomes available; and to restore the address in this queuing memory containing the found number; and PA1 means to read an address of a first sub-cell in the address memory, to the address restored by the means to find each number.
When the delay of a series of cells with a given time stamp expires, in other words when the time indicated by the label generator is equal to the sum of the given time stamp and the predetermined total delay, the first and the last storage address of this series are read in the site of the address memory corresponding to this time stamp. The link memory then supplies the complete series of addresses and permits reading in the buffer memory all the sub-cells of all the cells having the time stamp being considered. These cells are read in an order that is defined by the links in the link memory, but this order has no importance since all cells have the same time stamp and are addressed to a same output. The link memory is furthermore used to tie the different series of sub-cells from cells with successive time stamps in the same waiting line, which ensures their transmission in proper order. This linkage takes place by letting the link memory make the end of the series of sub-cell addresses of a cell correspond to the start of the series of sub-cell addresses of the cell to be transmitted next.
The first inconvenience of this device is that it cannot reset the order of cells arriving at the same input, which are intended for several outputs, in particular if the same cell is to be diffused to several outputs. This inability results from the function principle of this known device, because it is necessary to store, in each site of the address memory, a starting address of the address series and an ending address of the address series of the sub-cells; and it requires a link memory to link all the sub-cells that will subsequently be emitted from the same output. The resequencing devices associated with the different outputs of a node thus function independently of each other.
This known device has the further inconvenience of not permitting long cell lengths. Each site of the address memory corresponds to a unit of time of the generator that produces the time stamps. This unit of time is equal to the duration of a sub-cell. The time stamp generator does not have infinite capacity. It therefore periodically produces identical label values. Each site of the address memory is read with a constant period, at most equal to the period of the time stamp generator. At the moment a site is read, the make-up of the list must be terminated, so that an address from the end of the list can be properly read in the site under consideration. Thus, the period of the time stamp generator limits the number of sub-cells corresponding to that list, and finally limit the number of sub-cells each cell can contain.
Furthermore, it is not possible to increase the period of the time stamp generator indefinitely, because this requires increasing the number of bits of each cell to form a time stamp.